package leetcode77双周赛;

public class Three {

	public static int solution(int m,int n,int g[][],int w [][]) {
		int ans = 0;
		int res [][] = new int [m][n];
		for(int arr [] : w) {
			res[arr[0]][arr[1]] = -1;
		}
		for(int arr[] : g)
			dfs(m,n,res,arr[0],arr[1]);
//		for(int )
		return ans;
	}
	static void  dfs(int m,int n,int res[][],int x,int y) {
		for(int arr [] : dirs ) {
			int nx = x + arr[0];
			int ny = y + arr[1];
			if(nx < 0 || ny < 0 || nx >= m || ny >= n || res[nx][ny] == -1)
				continue;
			res[nx][ny] = 1;
			dfs(m,n,res,nx,ny);
			break;
		}
	}
	static void process(int m,int n,int x,int y,int dir[],int res[][]) {
//		if(res[x][y] )
		int nx = x + dir[0];
		int ny = y + dir[1];
		if(nx < 0 || ny < 0 || nx >= m || ny >= n || res[nx][ny] == -1)
			return ;
		process(m,n,nx,ny,dir,res);
	}
	/**
	 * 30 ms 左右 
	 * TLE  还是 ac  就在 
	 * 	for(int arr[] : g)
			//  守卫 所在的 位置 直接默认 就是  能守卫 的
			res[arr[0]][arr[1]] = -2;
		这一段 代码 上面  
		我感觉 这个 dfs 还是  可以 优化的 
	 */
	static int dirs[][] = {{1,0},{-1,0},{0,1},{0,-1}};
	static int solutionOne(int m,int n,int g[][],int w[][]) {
		int ans = 0;
		int res [][] = new int [m][n];
		// 先把 强 标为 -1 
		for(int arr [] : w) {
			res[arr[0]][arr[1]] = -1;
		}
		for(int arr[] : g)
			//  守卫 所在的 位置 直接默认 就是  能守卫 的
			res[arr[0]][arr[1]] = -2;
		// 能 保卫 直接  赋值 为 1；
		for(int  i [] : g) {
			for(int dir[] : dirs) {
//				if(res[])
				dfsOne(m,n,res,i[0] + dir[0],i[1] + dir[1],dir);
			}
		}
		for(int arr [] : res) {
			for(int i : arr) {
				//  注意 墙体 是 不计算在内 的 
				if(i == 0)
					ans++;
			}
		}
		return ans;
	}
	static void dfsOne(int m,int n,int res[][],int x,int y,int dir[]) {
		/**
		 * 只 做了 边界 判断  和 wall 体 判断 
		 * res[x][y] == -2 
		 * 直接  return 啥意思 就是 
		 * 当前的  guard1 在 某个  直线  方向 上 遇到了 另外 一个 guard2  
		 * 那 当前的 直线方向 就直接 交给    guard2 处理 就行 （这是 一个 小小的  剪枝 优化 ）
		 */
		if(x < 0 || y < 0 || x >= m || y >= n || res[x][y] == -1 || res[x][y] == -2)
			return ;
//		return 0;
		res[x][y] = 1;
		dfsOne(m,n,res,x + dir[0],y + dir[1],dir);
	}
}
/**
 * 17 ms 左右 
 * @author I adore you
 *
 */
class SArignote {

	public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
		int grid[][] = new int[m][n], count = 0;
		for (int[] guard : guards) {
			grid[guard[0]][guard[1]] = 2;
		}
		for (int[] wall : walls) {
			grid[wall[0]][wall[1]] = 2;
		}
		for (int[] guard : guards) {
			for (int i = guard[0] - 1; i >= 0 && grid[i][guard[1]] < 2; i--) {
				grid[i][guard[1]] = 1;
			}
			for (int i = guard[0] + 1; i < grid.length && grid[i][guard[1]] < 2; i++) {
				grid[i][guard[1]] = 1;
			}
			for (int i = guard[1] - 1; i >= 0 && grid[guard[0]][i] < 2; i--) {
				grid[guard[0]][i] = 1;
			}
			for (int i = guard[1] + 1; i < grid[0].length && grid[guard[0]][i] < 2; i++) {
				grid[guard[0]][i] = 1;
			}
		}
		for (int[] i : grid) {
			for (int j : i) {
				count += 1 - Math.min(1, j);
			}
		}
		return count;
	}
}
